<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /**
 * 最少硬币找零问题的一个变种 硬币找零问题是给出要找零的钱数 以及可用的硬币面额d1...dn及其数量 找出有多少种找零方法 最少硬币找零问题是给出要找零的钱数
 * 以及可用的硬币面额d1..dn及其数量 找到所需的最少的硬币个数
 */
    // 美国有以下面额（硬币）：d1=1，d2=5，d3=10，d4=25。 
    // 如果要找36美分的零钱，我们可以用1个25美分、1个10美分和1个便士（1美分）。 
    // 如何将这个解答转化成算法
    /**
     * 
     * @param {*} coins 面额 例如[1,5,10,25]
     */
    function MinCoinChange (coins) {
      var coins = coins // 1. 包含硬币面额的数组
      var cache = {} // 2. 用于存储已计算结果的缓存对象
      this.makeChange = function (amount) { // amount 零钱
        var me = this
        if (!amount) { // 3如果amount不为正 返回空数组
          return []
        }
        if (cache[amount]) { // 如果缓存中存在amount对应的结果 直接从缓存中返回结果 避免重复计算
          return cache[amount]
        }
        var min = [], newMin, newAmount
        for (var i = 0; i < coins.length; i++) { // 5 遍历硬币数组 对每个硬币进行处理
          var coin = coins[i]
          newAmount = amount - coin // 6 计算剩余金额
          if (newAmount >= 0) { // 剩余金额大于等于0 递归调用makeChange 函数来计算剩余金额的最小硬币数
            newMin = me.makeChange(newAmount) // 7
          } // 8 9 10
          // 如果剩余金额大于等于0 并且新的的最小硬币数newMin的长度比当前最小硬币数min的长度小 或者当前最小硬币数为空数组 并且
          // 新的最小硬币数的长度不为0 或者剩余金额为0 则更新最小硬币数min
          if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
            min = [coin].concat(newMin)
            console.log('new min' + min + 'for' + amount); // 11 输出最小硬币数和对应的金额
          }
        }
        return (cache[amount] = min) // 将当前硬币加入最小硬币数min的开头并返回结果 同时将结果存入缓存中
      }
    }
    var minCoinChange = new MinCoinChange([1, 5, 10, 25])
    console.log(minCoinChange.makeChange(36));
  </script>
</body>

</html>